import java.util.Random;

public class FindKthLargest {
    Random rand = new Random();
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        int left = 0, right = len-1;
        int target = len-k;
        while (true) {
            int pivotIndex = findPivotIndex(nums, left, right);
            if (pivotIndex == target) return nums[target];
            else if (target < pivotIndex) {
                right = pivotIndex - 1;
            }else {
                left = pivotIndex + 1;
            }
        }
    }

    private int findPivotIndex(int[] nums, int left, int right) {
        int randomIndex = left + rand.nextInt(right - left + 1);
        swap(nums, left, randomIndex);
        int pivot = nums[left];
        int i = left + 1, j = right;
        while (true) {
            while (i <= j && nums[i] < pivot) i++;
            while (i <= j && nums[j] > pivot) j--;
            if (i >= j) break;
            swap(nums, i, j);
            i++;
            j--;
        }
        swap(nums, left, j);
        return j;
    }

    private void swap(int[] nums, int left, int right) {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }

    public static void main(String[] args) {
        FindKthLargest obj = new FindKthLargest();
        int[] nums = {3,2,1,5,6,4};
        System.out.println(obj.findKthLargest(nums, 2));
    }
}
